#include <cstdio>
#include <queue>
#include <cstring>

using namespace std;

// Dinic 
#define F_INF (1<<29) 
#define MAXV 110 
#define MAXE 3010 // E*2! 
/*
struct MaxFlow{
    int V,E;
    int cap[MAXE],flow[MAXE];
    int to[MAXE],prev[MAXE],last[MAXV],used[MAXV],level[MAXV];

    void init(int n){
        V=n; E=0;
        int i; for(i=0;i<V;i++) last[i]=-1;
    }

    void add_edge(int x, int y, int f){
        cap[E]=f; flow[E]=0; to[E]=y; prev[E]=last[x]; last[x]=E; E++;
        cap[E]=0; flow[E]=0; to[E]=x; prev[E]=last[y]; last[y]=E; E++;
    }

    bool bfs(int s, int t){
        int i;
        for(i=0;i<V;i++) level[i]=-1;
        queue<int> q;
        q.push(s); level[s]=0;
        while(!q.empty()){
            int x = q.front(); q.pop();
            for(i=last[x];i>=0;i=prev[i]) if(level[to[i]]==-1&&cap[i]>flow[i]){q.push(to[i]); level[to[i]]=level[x]+1;}
        }
        return (level[t]!=-1);
    }
    int dfs(int v, int t, int f){
        int i;
        if(v==t)return f;
        for(i=used[v];i>=0;used[v]=i=prev[i])if(level[to[i]]>level[v]&&cap[i]>flow[i]){
            int tmp=dfs(to[i],t,min(f,cap[i]-flow[i]));
            if(tmp>0) {flow[i]+=tmp; flow[i^1]-=tmp; return tmp;}
        }
        return 0;
    }

    int maxflow(int s, int t){
        int i;
        while(bfs(s,t)){
            for(i=0;i<V;i++) used[i]=last[i];
            while(dfs(s,t,F_INF)!=0);
        }
        int ans=0;
        for(i=last[s];i>=0;i=prev[i]) ans+=flow[i];
        return ans;
    }
};
*/

const int MAXN=110;
const int MAXM=3010;
struct edge
{
    int v,next,val;
};
edge e[MAXM];
int p[MAXN],eid;
int h[MAXN],gap[MAXN],source,sink;
inline void insert(int from,int to,int val)
{
    e[eid].v=to;
    e[eid].val=val;
    e[eid].next=p[from];
    p[from]=eid++;

    e[eid].v=from;
    e[eid].val=0;
    e[eid].next=p[to];
    p[to]=eid++;    
}
inline int dfs(int pos,int cost,int cnt)
{
    if (pos==sink) return cost;
    int j,minh=cnt-1,lv=cost,d;
    for (j=p[pos];j!=-1;j=e[j].next)
    {
        int v=e[j].v,val=e[j].val;
        if (val>0)
        {
            if (h[v]+1==h[pos])
            {
                if (lv<e[j].val) d=lv;
                else d=e[j].val;
                d=dfs(v,d,cnt);
                e[j].val-=d;
                e[j^1].val+=d;
                lv-=d;
                if (h[source]>=cnt) return cost-lv;
                if (lv==0) break;
            }
            if (h[v]<minh) minh=h[v];
        }
    }
    if (lv==cost)
    {
        --gap[h[pos]];
        if (gap[h[pos]]==0) h[source]=cnt;
        h[pos]=minh+1;
        ++gap[h[pos]];
    }
    return cost-lv;
}
int sap(int st,int ed,int cnt)
{
    source=st;
    sink=ed;
    int ret=0;
    memset(gap,0,sizeof(gap));
    memset(h,0,sizeof(h));
    gap[st]=cnt;
    while (h[st]<cnt)
        ret+=dfs(st,F_INF,cnt);
    return ret;
}




int n, m, ansa, ansb;
int u[ MAXE ], v[ MAXE ], w[ MAXE ], pp[ MAXE ], r[ MAXV ], q[ 12 ], qn;
bool visit[ MAXE ];


void init( )
{
    int i;
    qn = 0;
    for ( i = 1; i <= n; i++ )
        scanf("%d", &r[ i ]);
    qn = 0;
    for ( i = 0; i < m; i++ )
    {
        scanf("%d%d%d%d", &u[ i ], &v[ i ], &w[ i ], &pp[ i ]);
        if ( pp[ i ] > 0 )
            q[ qn++ ] = i;
    }
    eid = 0;
    memset( p, -1, sizeof( p ) );
    for ( i = 1; i <= n; i++ )
        insert( 0, i, r[ i ] );
    for ( i = 0; i < m; i++ )
        if ( pp[ i ] < 0 )
        {
            insert( u[ i ], n + 1, w[ i ] );
            insert( u[ i ], v[ i ], F_INF );
        }
        else if ( pp[ i ] == 0 )
        {
            insert( u[ i ], v[ i ], F_INF );
        }
        else
        {
            insert( u[ i ], v[ i ], F_INF );
        }
    ansa = sap( 0, n + 1, n + 2 );
    ansb = 1000000000;
    memset( visit, 0, sizeof( visit ) );
}

void dfs( int k, int cost )
{
    int i, t;
    if ( cost >= ansb ) return ;
    eid = 0;
    memset( p, -1, sizeof( p ) );
    for ( i = 1; i <= n; i++ )
        insert( 0, i, r[ i ] );
    for ( i = 0; i < m; i++ )
        if ( pp[ i ] < 0 )
        {
            insert( u[ i ], n + 1, w[ i ] );
            insert( u[ i ], v[ i ], F_INF );
        }
        else if ( pp[ i ] == 0 )
        {
            insert( u[ i ], v[ i ], F_INF );
        }
        else
        {
            if ( visit[ i ] )
                insert( u[ i ], v[ i ], F_INF );
            else
                insert( u[ i ], v[ i ], 1 );
        }
    t = sap( 0, n + 1, n + 2 );
    if ( ansa == t )
        ansb = cost;
    for ( i = k; i < qn; i++ )
    {
        visit[ q[ i ] ] = 1;
        dfs( i + 1, cost + w[ q[ i ] ] );
        visit[ q[ i ] ] = 0;
    }
}

int main( )
{
    while ( scanf("%d%d", &n, &m) != EOF )
    {
        init( );
        if ( ansa == 0 )
        {
            puts("Poor Heaven Empire");
            continue;
        }
        dfs( 0, 0 );
        printf("%d %d\n", ansa, ansb);
    }
    return 0;
}
